UVa/10149 - Yahtzee/axy.cpp

   1 /*
   2 we can use 13 bits to record which category is used,
   3 one category is used is represented by setting a bit as follows,
   4
   5 for (int combi = 0, add = 1 << c; combi < ncombinations; ++combi) {
   6
   7 Here, combi represents the bit combination, and add is the new added category.
   8
   9 Secondly, we can use DP to find the best categorization
  10 for each upper score (upper score refers to the sum score of the first
  11 six categories).
  12 We need to record each of the 64 ([0, 63]) upper score conditions, and
  13 if a new higher score with the same upper score could be achieved by
  14 a new categorization, we could adjust the old categorization
  15 for this new one as follows,
  16
  17 int newscore = score + dp[combi][u];
  18 int newupper = upper + u < nupper ? upper + u : nupper - 1;
  19 if (newscore > dp[combi|add][newupper]) {
  20  dp[combi|add][newupper] = newscore;
  21  previous[combi|add][newupper].combi = combi;
  22  previous[combi|add][newupper].upper = u;
  23 }
  24
  25 Here, previous is used to restore the categorization.
  26
  27 At last, we check for the best score within the upper scores
  28 of full categorization, and give a bonus for the upper score of 63 as folllows,
  29
  30  int combi = ncombinations - 1;
  31  int upper = nupper - 1;
  32  bonus = 35;
  33  score = dp[combi][upper] + bonus;
  34  for (int u = 0; u < nupper; ++u) {
  35    if (score < dp[combi][u]) {
  36      bonus = 0;
  37      score = dp[combi][u];
  38      upper = u;
  39    }
  40  }
  41 */
  42 /*
  43    Sebastian Arcila Valenzuela
  44    sebastianarcila@gmail.com
  45    2009
  46    @(#)TEMPLATE.c.tpl
  47  */
  48
  49 /*#include <config.h>
  50 #include "10149.h"
  51 */
  52 #include <stdio.h>
  53 #include <string.h>
  54 #include <stdlib.h>
  55 #include <math.h>
  56 #include <limits.h>
  57 #include <assert.h>
  58 #include <stdarg.h>
  59 #include <string>
  60 #include <sstream>
  61 #include <iostream>
  62 #include <fstream>
  63 #include <iterator>
  64 #include <algorithm>
  65 #include <vector>
  66 #include <deque>
  67 #include <list>
  68 #include <queue>
  69 #include <stack>
  70 #include <set>
  71 #include <bitset>
  72
  73 using namespace std;
  74
  75 /* DEBUG */
  76 #define D(x) cerr<<__LINE__<<" "#x" "<<x<<endl
  77 #define D_v(x) for(int i=0;i<x.size();cerr<<x[i++]<<" ")
  78
  79 #define ALL(x) x.begin(),x.end()
  80 struct rec
  81 {
  82   int combi;
  83   int upper;
  84 };
  85 const int n_c = 13, n_r = 13,n_d = 5,combinations = 8192,nupper = 64;
  86
  87 int pop_count[combinations], dp[combinations][nupper], scores[n_r][n_c], categorization[n_c];
  88
  89 rec previous[combinations][nupper];
  90
  91 int eval(const int &category,const int dices[])
  92 {
  93   int c = category + 1,score = 0;
  94   switch (c)
  95   {
  96   case 1:
  97   case 2:
  98   case 3:
  99   case 4:
 100   case 5:
 101   case 6:
 102     for (int i = 0; i < n_d; ++i)
 103       if (dices[i] == c)
 104         score += c;
 105     break;
 106   case 7:
 107     for (int i = 0; i < n_d; ++i)
 108       score += dices[i];
 109     break;
 110   case 8:
 111     if (dices[0] == dices[2] || dices[1] == dices[3] ||
 112         dices[2] == dices[4])
 113       for (int i = 0; i < n_d; ++i)
 114         score += dices[i];
 115     break;
 116   case 9:
 117    if (dices[0] == dices[3] || dices[1] == dices[4])
 118      for (int i = 0; i < n_d; ++i)
 119        score += dices[i];
 120    break;
 121   case 10:
 122     if (dices[0] == dices[4])
 123       score = 50;
 124     break;
 125   case 11:
 126     if (dices[0] == dices[1]-1 && dices[1] == dices[2]-1 &&
 127        dices[2] == dices[3]-1 || dices[1] == dices[2]-1 &&
 128        dices[2] == dices[3]-1 && dices[3] == dices[4]-1)
 129       score = 25;
 130     break;
 131   case 12:
 132     if (dices[0] == dices[1]-1 && dices[1] == dices[2]-1 &&
 133         dices[2] == dices[3]-1 && dices[3] == dices[4]-1)
 134       score = 35;
 135     break;
 136   case 13:
 137     if (dices[0] == dices[1] && dices[2] == dices[4] ||
 138         dices[0] == dices[2] && dices[3] == dices[4])
 139       score = 40;
 140     break;
 141   }
 142   return score;
 143 }
 144
 145
 146
 147 void do_it(int& bonus, int& score)
 148 {
 149
 150   for (int i = 0; i < combinations; ++i)
 151     for (int j = 0; j < nupper; ++j)
 152       dp[i][j] = INT_MIN;
 153
 154   dp[0][0] = 0;
 155
 156   for (int r = 0; r < n_r; ++r)
 157     for (int c = 0; c < n_c; ++c)
 158       {
 159         int score = scores[r][c];
 160         int upper = c < 6 ? score : 0;
 161         for (int combi = 0, add = 1 << c; combi < combinations; ++combi)
 162           {
 163             if (pop_count[combi] != r || combi & add) continue;
 164             for (int u = 0; u < nupper; ++u)
 165               {
 166                 int newscore = score + dp[combi][u];
 167                 int newupper = upper + u < nupper ? upper + u : nupper - 1;
 168                 if (newscore > dp[combi|add][newupper])
 169                   {
 170                     dp[combi|add][newupper] = newscore;
 171                     previous[combi|add][newupper].combi = combi;
 172                     previous[combi|add][newupper].upper = u;
 173                   }
 174               }
 175           }
 176       }
 177
 178   int combi = combinations - 1;
 179   int upper = nupper - 1;
 180   bonus = 35;
 181   score = dp[combi][upper] + bonus;
 182   for (int u = 0; u < nupper; ++u)
 183     if (score < dp[combi][u])
 184       {
 185         bonus = 0;
 186         score = dp[combi][u];
 187         upper = u;
 188       }
 189
 190   while (combi)
 191     {
 192       rec pre = previous[combi][upper];
 193       int c = 0;
 194       for (int add = combi ^ pre.combi; add >>= 1; ++c);
 195       categorization[c] = dp[combi][upper] - dp[pre.combi][pre.upper];
 196       combi = pre.combi;
 197       upper = pre.upper;
 198     }
 199 }
 200
 201 int main()
 202 {
 203
 204   /* Calcula todas las categorias de cada combinacion*/
 205   for (int i = 0; i < combinations; ++i)
 206     pop_count[i] = __builtin_popcount(i);
 207
 208   int dices[n_d];
 209   int d = 0, r = 0, g = 0;
 210   while (scanf("%d",&dices[d++ % n_d]) == 1)
 211     {
 212       if (d / n_d > r)
 213         {
 214           sort(dices, dices + n_d);
 215           for (int c = 0; c < n_c; ++c)
 216             scores[r % n_r][c] = eval(c,dices);
 217
 218           r = d / n_d;
 219         }
 220       if (r / n_r > g)
 221         {
 222           g = r / n_r;
 223           int bonus = 0;
 224           int score = 0;
 225           do_it(bonus, score);
 226           for (int c = 0; c < n_c; ++c)
 227             printf("%d ",categorization[c]);
 228
 229           printf("%d %d\n",bonus,score);
 230         }
 231     }
 232
 233   return 0;
 234 }
 235
 236